package leetcode;

import util.PrintArray;

import java.util.LinkedHashMap;
import java.util.Random;

/**
 * Created by shuowu on 2018/1/11.
 */
public class LRUCache_1 {
    private LinkedHashMap<String, Integer> record;
    private int mMaxRecord;
    private int mCurRecord;

    public static void main(String[] args){
//        String[] test = {"1", "2", "3", "4", "5", "6", "7"};
//        int[] array = {1, 2, 3, 4, 5, 6, 7};
//
//        int[] putIndex = {0, 3, 1, 2, 4, 0, 1};
//
        LRUCache_1 object = new LRUCache_1(4);
//        Random random = new Random();
//        for (int i = 0; i < 6; i++){
//            object.put(test[putIndex[i]], array[putIndex[i]]);
//            int curValue = lruCache_1.get(test[putIndex[0]]);
//            System.out.println("get key is " + curValue);
//        }

//        int[] array1 = {1, 4, 7, 10, 18};
//        int[] array2 = {0, 2, 7, 8, 8};
//        int[] array = new int[10];
//        object.merge(array, array1, array2);

        int[] array = {2, 4, 6, 0, 2, 14, 5, 2, 1, 5, -4, -5, -80, 10, 23, 13, 53, -6};
        object.mergeSort(array);
        PrintArray.printArray(array);
    }

    public LRUCache_1(int maxRecord) {
        record = new LinkedHashMap<>();
        mMaxRecord = maxRecord;
    }

    public void put(String key, int value) {
        if (!record.containsKey(key)) {
            mCurRecord++;
            if (mCurRecord > mMaxRecord) {
                String firstKey = record.entrySet().iterator().next().getKey();
                record.remove(firstKey);
            }
        } else {
            record.remove(key);
        }
        //如果已经有了，这个不会更新到最前面
        record.put(key, value);
    }

    //LRU get的时候也需要重新回到最前面
    public int get(String key){
        if (!record.containsKey(key)) {
            System.out.println("don't contain the key");
            return 0;
        }
        int value = record.get(key);
        record.remove(key);
        record.put(key, value);
        return record.get(key);
    }

    public int binarySearch(int[] array, int left, int right, int value){
        if(array == null || array.length <= 0){
            return -1;
        }
        int middle = left + (right - left) >> 1;
        while (left <= right) {
            if(array[middle] == value){
                return middle;
            } else if(array[middle] < value){
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return -1;
    }

    // 找到第一个等于或者最接近的小于某个值的下标
    public int binarySearchLess(int[] array, int left, int right, int value){
        if(array == null || array.length <= 0){
            return -1;
        }
        int middle = left + (right - left) >> 1;
        while (left < right) {
            if(array[middle] <= value){
                left = middle;
            } else {
                right = middle - 1;
            }
            if(left >= right - 1){
                break;
            }
        }
        return array[right] <= value ? right : left;
    }

    //归并排序
    public void mergeSort(int[] nums) {
        if(nums == null || nums.length <= 0){
            return;
        }
        //表示有序的长度
        int length = 1;
        while (length <= nums.length) {
            for (int j = 0; j < nums.length - length; j += length *2) {
                int low = j;
                int mid = low + length - 1;
                int high = low + length * 2 - 1;
                if (high > nums.length - 1) {
                    high = nums.length - 1;
                }
                merge(nums, low, mid, high);
            }
            length *= 2;
        }
    }

    // 对数组nums作归并递归排序
    //low表示第一个排序的序列的起始下标，mid为第一个排序的序列的终点下标
    //high表示第二个排序序列的终点下标
    public void merge(int[] nums, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int firstIndex = low;
        int secondIndex = mid + 1;
        for(int i = 0; i < temp.length; i++) {
            if(firstIndex > mid){
                temp[i] = nums[secondIndex++];
            } else if(secondIndex > high) {
                temp[i] = nums[firstIndex++];
            } else {
                temp[i] = nums[firstIndex] < nums[secondIndex] ? nums[firstIndex++] : nums[secondIndex++];
            }
        }
        for(int i = low; i <= high; i++){
            nums[i] = temp[i - low];
        }
    }

    public void merge(int[] array, int[] sort1, int[] sort2){
        if (sort1 == null || sort1.length <= 0 || sort2 == null || sort2.length <= 0) {
            return;
        }
        int index1 = 0;
        int index2 = 0;
        for (int i = 0; i < array.length; ) {
            if (index1 >= sort1.length) {
                array[i++] = sort2[index2++];
            } else if (index2 >= sort2.length) {
                array[i++] = sort1[index1++];
            } else if(sort1[index1] <= sort2[index2]){
                array[i++] = sort1[index1++];
            } else {
                array[i++] = sort2[index2++];
            }
        }
    }
}

/**
public class LRUCache {

    private Map<Integer, Integer> map;

    public LRUCache(int capacity) {
        map = new LinkedCappedHashMap<>(capacity);
    }

    public int get(int key) {
        if(!map.containsKey(key)) { return -1; }
        return map.get(key);
    }

    public void put(int key, int value) {
        map.put(key,value);
    }

    private static class LinkedCappedHashMap<K,V> extends LinkedHashMap<K,V> {

        int maximumCapacity;

        LinkedCappedHashMap(int maximumCapacity) {
            super(16, 0.75f, true);
            this.maximumCapacity = maximumCapacity;
        }

        protected boolean removeEldestEntry(Map.Entry eldest) {
            return size() > maximumCapacity;
        }
    }
}
*/